#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/12 17:18
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _40_combinationSum2.py
from copy import deepcopy


class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        path = []
        use = [False] * len(candidates)
        candidates = sorted(candidates)

        def dfs(index, target):
            if target < 0:
                return
            if target == 0:
                res.append(deepcopy(path))
                return

            for i in range(index, len(candidates)):  # # 放入idnex只是为了保存顺序
                if use[i]:continue
                if target - candidates[i] < 0: continue
                if i>0 and candidates[i] == candidates[i-1] and not use[i-1]: continue
                use[i] = True
                path.append(candidates[i])
                dfs(i+1, target - candidates[i])
                use[i] = False
                path.pop()

        dfs(0, target)
        return res
